package com.practice.niuke.new_direct_basics.class06;

import java.util.*;

/**
 * kruskal算法
 * 适用范围： 要求无向图(undirected graph only)
 */
public class Code04_Kruskal {

	/**
	 * 进行 kruskal算法 的辅助结构（Querry） 伪代码描述
	 */
	public static class Querry{

		// 某个描述多个小集合的数据结构;(标准实现是需要用并查集)

		public Querry(Collection<Node> nodes){
			// Query内部把每一个节点放到，单独的小集合里去
		}

		/**
		 * a节点和b节点是否属于一个集合
		 *
		 * @param a
		 * @param b
		 * @return
		 */
		public boolean isSameSet(Node a, Node b){
			return true;
		}

		/**
		 * 把a节点所在集合的所有节点 和 b节点所在集合的所有节点，合并成一个大集合。
		 *
		 * @param a
		 * @param b
		 */
		public void union(Node a, Node b){

		}
	}

	/**
	 * 进行 kruskal算法 的辅助结构（Querry） 我们自己的代码实现
	 */
	public static class MySets{
		// 某个描述多个小集合的数据结构,
		// HashMap<Node, List<Node>>: 节点Node，节点Node所在的小集合（这里定义成一个List）
		public HashMap<Node, List<Node>>  setMap;
		public MySets(List<Node> nodes) {
			// Query内部把每一个节点放到，单独的小集合里去
			for(Node cur : nodes) {
				List<Node> list = new ArrayList<Node>();
				list.add(cur);
				setMap.put(cur, list);
			}
		}

		/**
		 * a节点和b节点是否属于一个集合
		 * @param from a节点
		 * @param to b节点
		 * @return boolean
		 */
		public boolean isSameSet(Node from, Node to) {
			List<Node> fromSet  = setMap.get(from);
			List<Node> toSet = setMap.get(to);
			return fromSet == toSet;
		}

		/**
		 * 把a节点所在集合的所有节点 和 b节点所在集合的所有节点，合并成一个大集合。
		 * @param from a节点
		 * @param to b节点
		 */
		public void union(Node from, Node to) {
			List<Node> fromSet  = setMap.get(from);
			List<Node> toSet = setMap.get(to);
			for(Node toNode : toSet) {
				fromSet.add(toNode);
				setMap.put(toNode, fromSet);
			}
		}
	}

	/**
	 * 进行 kruskal算法 的辅助结构（Querry） 标准代码实现（使用到了并查集// Union-Find Set）
	 */
	public static class UnionFind {
		// key 某一个节点， value key节点往上的节点
		private HashMap<Node, Node> fatherMap;
		// key 某一个集合的代表节点, value key所在集合的节点个数
		private HashMap<Node, Integer> sizeMap;

		public UnionFind() {
			fatherMap = new HashMap<Node, Node>();
			sizeMap = new HashMap<Node, Integer>();
		}
		
		public void makeSets(Collection<Node> nodes) {
			fatherMap.clear();
			sizeMap.clear();
			for (Node node : nodes) {
				fatherMap.put(node, node);
				sizeMap.put(node, 1);
			}
		}

		private Node findFather(Node n) {
			Stack<Node> path = new Stack<>();
			while(n != fatherMap.get(n)) {
				path.add(n);
				n = fatherMap.get(n);
			}
			while(!path.isEmpty()) {
				fatherMap.put(path.pop(), n);
			}
			return n;
		}

		public boolean isSameSet(Node a, Node b) {
			return findFather(a) == findFather(b);
		}

		public void union(Node a, Node b) {
			if (a == null || b == null) {
				return;
			}
			Node aDai = findFather(a);
			Node bDai = findFather(b);
			if (aDai != bDai) {
				int aSetSize = sizeMap.get(aDai);
				int bSetSize = sizeMap.get(bDai);
				if (aSetSize <= bSetSize) {
					fatherMap.put(aDai, bDai);
					sizeMap.put(bDai, aSetSize + bSetSize);
					sizeMap.remove(aDai);
				} else {
					fatherMap.put(bDai, aDai);
					sizeMap.put(aDai, aSetSize + bSetSize);
					sizeMap.remove(bDai);
				}
			}
		}
	}

	/**
	 * 比较器：
	 * 以边的权值作为比较，权值小的排在前面。
	 */
	public static class EdgeComparator implements Comparator<Edge> {

		@Override
		public int compare(Edge o1, Edge o2) {
			return o1.weight - o2.weight;
		}

	}

	/**
	 * kruskal算法
	 *
	 * @param graph
	 * @return
	 */
	public static Set<Edge> kruskalMST(Graph graph) {
//		UnionFind querry = new UnionFind();
//		querry.makeSets(graph.nodes.values());
		// 初始化我们的辅助结构
		Collection<Node> nodes = graph.nodes.values();
		Querry querry = new Querry(nodes);

		// 由于我们是从小到大的考虑所有的边，因此准备一个存放边的小根堆。（比较器，以边的权值进行比较）
		PriorityQueue<Edge> priorityQueue = new PriorityQueue<>(new EdgeComparator());
		// 将图中所有的边存入小根堆
		for (Edge edge : graph.edges) { // M 条边
			priorityQueue.add(edge);  // O(logM)
		}
		// 记录结果的集合
		Set<Edge> result = new HashSet<>();
		// 当存放边的小根堆不为空时
		while (!priorityQueue.isEmpty()) { // M 条边
			// 从小根堆中弹出一条边
			Edge edge = priorityQueue.poll(); // O(logM)
			// 考察这条边两边的节点是否属于同一个集合
			if (!querry.isSameSet(edge.from, edge.to)) { // O(1)
				// 这条边两边的节点不属于同一个集合，将这条边放入结果集合
				result.add(edge);
				// 合并这条边两边的节点所在的集合
				querry.union(edge.from, edge.to);
			}
		}
		return result;
	}
}
